Компьютерная графика

Наука и искусство визуальной коммуникации посредством компьютерного дисплея и инструментом интерактивного взаимодействия с ним.

Мультидисциплинарность

Связь с компьютерным зрением

Компьютерная графика: реализация с определенного ракурса внешнего вида сцены, в которую погружены модели объектов под заданными условиями освещения.

Компьютерное зрение: определение параметров сцены и погруженных в нее объектов при заданных допущениях.

:scale 75%

.small[Lesage, Visvalingam, 2002]

Графический конвейер

:scale 85%

.small[Hughes et al, 2013]

Графический конвейер

:scale 80%

Взаимодействие с пользователем может оказывать влияние на последующее поведение графического приложения

Графический конвейер 2D-приложения

.pull-left[ ]

.pull-right[ Графическая платформа отвечает за взаимодействие приложения и оборудования

Модель приложения (application model) представляет визуализируемые данные

Клиентская область (client area) определяет пространство, в котором приложение выполняет отрисовку.

Порт просмотра (viewport) определяет часть клиентской области, где генератор сцены выполняет отрисовку модели ]

Эволюция графической платформы

1980-е — начало 1990-х (Apple QuickDraw, Microsoft GDI): отрисовка пикселей на прямоугольной канве в целочисленных координатах. Отрисовка .red[примитивов]: геометрических форм или битмапов (пиксельных карт). - Точка \((0,0)\) располагается в левом верхнем углу. - Каждый примитив заполняется путем вызова определенной функции (например, FillRectangle). - Размер объекта зависит от разрешения объекта. Более низкое разрешение (крупные пикселы) — больше размеры объектов.

Середина 1990-х — н.вр. Переход к координатам с плавающей точкой позволил решить проблему зависимости размера изображения от системы координат.

Непосредственный режим

В .blue[непосредственном режиме] (immediate mode) клиент через графическую платформу обращается непосредственно к выводящему устройству. - Запись примитивов, переданных приложением, не выполняется. - При смене сцены приложение должно перерисовать ее целиком.

Сохраненный режим

В .red[сохраненном режиме] (retained mode) графическая платформа хранит спецификацию сцены в виде специализированной базы данных, которая называется графом сцены (scene graph). - Объекты могут добавляться в граф сцены последовательно. - Каждое изменение графа приводит к перерисовке сцены

Процедурный и декларативный подходы

.blue[Процедурный код] пишется на императивном языке программирования - Описывает действия - Стандарт при взаимодействии с графической платформой - В геоинформационных пакетах применяется на низком уровне, невидимом для пользователя

.red[Декларативные спецификации] фиксируются на языке разметки - Описывают результаты - Вспомогательное средство в графических платформах - В геоинформационных пакетах применяется на высоком уровне при описании стилей карт (CSS, LYR, QML, SLD, YSLD)

Процедурный код

Классический низкоуровневый пример — отрисовка линии.

draw_line(x0, y0, x1, y1)

:scale 70%

.blue[Алгоритм Брэзенхема] .small[Bresenham, J. E. (1965). “Algorithm for computer control of a digital plotter” (PDF). IBM Systems Journal. 4 (1): 25–30. doi:10.1147/sj.41.0025.]

Алгоритм Брезенхэма

Cистема экранных координат \(XY\), где \(X\) — столбец (увеличивается слева направо), \(Y\) — строка (увеличивается сверху вниз)

Уравнение отрезка: \[\frac{y - y_0}{y_1-y_0} = \frac{x - x_0}{x_1-x_0}\] Выразив \(y\), получаем: \[y = \color{red}{\underbrace{\frac{y_1 - y_0}{x_1-x_0}}_{\textbf{d (уклон)}}} (x - x_0) + y_0\] —

Алгоритм Брезенхэма

Стандартно рассматривается отрисовка линии, которая располагается в секторе В-ЮВ, т.е. идет относительно начальной точки вправо и полого вниз при соблюдении следующих условий: - \(x_0 \geq 0,~y_0 \geq 0\); - \(x_0 < x_1,~y_0 \leq y_1\); - \(x_1 - x_0 \geq y_1 - y_0\). :scale 70%

Алгоритм Брезенхэма

Для сектора В-ЮВ алгоритм опирается на координаты \(x\):

.pull-left[Вычисляем заранее: - \(dx = x_1 - x_0\). - \(dy = y_1 - y_0\). - \(\color{blue}{d = dy / dx}\); - \(\color{blue}{y = y_0}\); - \(e = 0\)]

.pull-right[Для \(\color{blue}{x = x_0, ... x_1}\), выполняем: 1. Рисуем пиксель \((x, y)\). 2. Обновляем ошибку \(e = e + |d|\). 3. Если \(e \geq 0.5\), то: - \(\color{blue}{y = y + \texttt{sign}(dy)}\), - \(e = e - 1\).]

Использование функции \(\texttt{sign}\) позволяет применять алгоритм также и для сектора В-СВ (только \(y\) будет уменьшаться).

Обозначим этот случай как draw_line_byX(x0, y0, x1, y1)

Алгоритм Брезенхэма

.pull-left[Альтернативно рассматривается отрисовка линии, которая располагается в секторе Ю-ЮВ, т.е. идет относительно начальной точки вправо и круто вниз при соблюдении следующих условий: - \(x_0 \geq 0,~y_0 \geq 0\); - \(x_0 \leq x_1,~y_0 < y_1\); - \(x_1 - x_0 < y_1 - y_0\).]

.pull-right[:scale 70%]

Алгоритм Брезенхэма

Для сектора Ю-ЮВ алгоритм опирается на координаты \(y\):

.pull-left[Вычисляем заранее: - \(dx = x_1 - x_0\). - \(dy = y_1 - y_0\). - \(\color{red}{d = dx / dy}\); - \(\color{red}{x = x_0}\); - \(e = 0\)]

.pull-right[Для \(\color{red}{y = y_0, ... y_1}\), выполняем: 1. Рисуем пиксель \((x, y)\). 2. Обновляем ошибку \(e = e + |d|\). 3. Если \(e \geq 0.5\), то: - \(\color{red}{x = x + \texttt{sign}(dx)}\), - \(e = e - 1\).]

Использование функции \(\texttt{sign}\) позволяет применять алгоритм также и для сектора Ю-ЮЗ (только \(x\) будет уменьшаться).

Обозначим этот случай как draw_line_byY(x0, y0, x1, y1)

Алгоритм Брезенхэма

Для оставшихся направлений построение линий реализуется путем перестановки местами начальной и конечной точки. Код результирующей функции на языке Python:

def plot_line(x0, y0, x1, y1):
    if abs(y1 - y0) < abs(x1 - x0): # пологая линия
        if x0 > x1:
            plot_line_byX(x1, y1, x0, y0)
        else:
            plot_line_byX(x0, y0, x1, y1)
    else:
        if y0 > y1:                 # крутая линия
            plot_line_byY(x1, y1, x0, y0)
        else:
            plot_line_byY(x0, y0, x1, y1)

где abs() — функция вычисления модуля.

Заливка полигона

:scale 95%

Заливка полигона

.blue[Алгоритм сканирующей линии:]

Для каждого \(y_k = y_{min},...,y_{max}\) необходимо получить упорядоченное по возрастанию множество \(X = \{x_1, x_2, ..., x_n\}\) абсцисс точек его пересечения с исходными линиями: 1. Для каждой линии \(l_j, j = 1,...,N\): - вычислить флаг пересечения \(f: y^j_0 < y_k \neq y^j_1 < y_k\); - если \(f = \texttt{TRUE}\), то - вычислить \(x^j = x^j_0 + (x^j_1 - x^j_0)\frac{y_k - y^j_0}{y^j_1 - y^j_0}\); - добавить \(x^j\) в множество \(X\). 2. Если \(X\) не пусто, то упорядочить его по возрастанию и выполнить закрашивание между его элементами в порядке:

\[\lceil x_1 \rceil \to \lfloor x_2 \rfloor,~\lceil x_3 \rceil \to \lfloor x_4 \rfloor,~...~,~\lceil x_{n-1} \rceil \to \lfloor x_n \rfloor\]

Передискретизация (resampling)

Передискретизация необходима при визуализации растрового изображения на растровом экране. Как правило, разрешение этих растров не совпадает.

:scale 65%

Метод ближайшего соседа

Используется значение ближайшего пикселя:

:scale 70%

Метод билинейной интерполяции

Восстанавливается поверхность в ячейке из 4 узлов:

:scale 75%

Метод билинейной интерполяции

.left-40[ :scale 85%]

.right-60[ Коэффициенты определяются по 4 точкам: \[\begin{cases} a_{00} = f_{00},\\ a_{10} = f_{10} - f_{00},\\ a_{01} = f_{01} - f_{00},\\ a_{01} = f_{00} + f_{11} - f_{10} - f_{01}. \end{cases}\]

\[f(x, y) = a_{00} + a_{10}x + a_{01}y + a_{11}xy\]]

Координаты \(x\) и \(y\) меняются в диапазоне от \(0\) до \(1\) в пределах ячейки.

Метод бикубической интерполяции

Восстанавливается поверхность в 9 ячейках, окружающих узел:

:scale 75%

Метод бикубической интерполяции

.left-40[ :scale 95%]

.right-60[ Коэффициенты определяются по 16 точкам:

\[\begin{cases} f(0,0) = a_{00},\\ f(1,0) = a_{00} + a_{10} + a_{20} + a_{30},\\ f(0,1) = a_{00} + a_{01} + a_{02} + a_{03},\\ f(1,1) = \sum_{i=0}^3 \sum_{j=0}^3 a_{ij},\\ \dots \end{cases}\]

\[f(x, y) = \sum_{i=0}^3 \sum_{j=0}^3 a_{ij} x^i y^j\] ]

Координаты \(x\) и \(y\) меняются в диапазоне от \(0\) до \(1\) в пределах окрестности \(3 \times 3\) ячеек.

Передискретизация и фильтрация

.pull-left[ :scale 90% .small[Marschner et al., 2016]] .pull-right[ Передискретизацию можно также рассматривать как двухстадийный процесс: - Построение гладкой непрерывной функции путем применения реконструкционного фильтра

Передискретизация и фильтрация

Псевдокод одномерной передискретизации:

fun resample(sequence a, float x0, float dx, int n, filter f)
  b = list(length = n)
  for i = 0 to n-1 do
    b[i] = reconstruct(a, f, x0 + i * dx)
  return b

Параметр x0 отвечает за расположение первого элемента выборки в системе координат исходной последовательности.

Например, если этот элемент расположен посередине между 0-м и 1-м элементом исходной последовательности, то x0 = 0.5

Дискретно-непрерывная свёртка

Восстановление непрерывной поверхности происходит путем взвешенного осреднения исходных значений. Веса определяются свёрточным ядром: .left-60[ :scale 95%

.small[Marschner et al., 2016] ] .right-40[ Свертка есть результат произведения функций: \[(a \star f)(x) = \sum_i a[i] f(x-i)\]

Для ядра ограниченного радиуса \(r\): \[(a \star f)(x) = \sum_{i = \lceil x-r\rceil}^{\lfloor x+r \rfloor} a[i] f(x-i)\] ]

Дискретно-непрерывная свёртка

.left-60[ :scale 95%

.small[Marschner et al., 2016] ] .right-40[ Восстановленную функцию можно получить путем суммирования произведений фильтра и исходного значения в точках \(i\): \[(a \star f) = \sum_i a[i] f_{\to i}\]]

Дискретно-непрерывная свёртка

Псевдокод:

fun reconstruct(sequence a, filter f , real x)
  s=0
  r = f.radius
  for i = ⌈x − r⌉ to ⌊x + r⌋ do
    s = s + a[i]f (x − i) 
  return s

Популярные фильтры

:scale 70%

Передискретизация и фильтрация

Проблема передискретизации при даунсемплинге (понижении разрешения) заключается в появлении артефактов таких как муар (слева) и зубчатость (справа):

.small[Marschner et al., 2016]

Поэтому при понижении разрешения помимо реконструкционного фильтра необходимо использовать также сглаживающий.

Передискретизационный фильтр

Поскольку свёрточные фильтры можно перемножать, для комбинирования реконструкции и сглаживания достаточно провести фильтрацию один раз (диагональная стрелка):

:scale 65%

.small[Marschner et al., 2016]

Передискретизация и фильтрация

Прямоугольный домен изображения размером \(n_x \times n_y\):

\[R = [-0.5, n_x - 0.5] \times [-0.5, n_y - 0.5]\] :scale 55%

.small[Marschner et al., 2016]

Передискретизация и фильтрация

Псевдокод одномерной сглаживающей передискретизации:

fun resample(sequence a, float xmin, float xmax, int n, filter f)
  b = list(length = n)
  r = f.radius
  dx = (xmax - xmin)/n
  x0 = xmin + dx/2
  for i = 0 to n-1 do
    s = 0
    x = x0 + i * dx
    for j = ceil(x-r) to floor(x+r) do
      s = s + a[j] * f(x - j)
    b[i] = s
  return b

Параметры xmin и xmax обозначают минимальную и максимальную растровую координату по измерению X. Для полного изображения xmin = -0.5, xmax = nx - 0.5.

Фильтрация на границе растра

Если фильтр выходит за границу растра, возможно три варианта:

Метод бикубической интерполяции

Keys (1981) показал, что бикубическую реконструкцию можно реализовать путем свёртки с использованием следующего фильтра:

\[W(x) = \begin{cases} (a+2)|x|^3-(a+3)|x|^2+1 & \text{для } |x| \leq 1, \\ a|x|^3-5a|x|^2+8a|x|-4a & \text{для } 1 < |x| < 2, \\ 0 & \text{иначе}, \end{cases},\]

где \(a = -0.5\) или \(a = -0.75\).

R. Keys. Cubic convolution interpolation for digital image processing // IEEE Transactions on Acoustics, Speech, and Signal Processing — 1981. — Vol. 29, no. 6. — P. 1153—1160. — doi:10.1109/TASSP.1981.1163711

Сглаживание (antialiasing)

При крупном размере пиксела выводящего устройства ступенчатость линий и границ полигонов становится заметной.

Для устранения эффекта ступенчатости используется сглаживание (antialiasing).

:scale 75%

Вверху — со сглаживанием, внизу — без (.small[Marschner et al., 2016])

Сглаживание (antialiasing)

:scale 80%

.small[https://www.neogamr.net/what-is-anti-aliasing/]

Суперсемплинг (antialiasing)

Пусть результирующее растровое изображение \(R\) имеет размеры \(m \times n\).

  1. Создается буферное изображение \(R_b\) размером \(km \times kn\), где \(k \in \mathbb{N^*}\) — коэффициент сглаживания (положительное натуральное число).
  2. Объекты отрисовываются в \(R_b\).
  3. Производится передискретизация \(R_b \to R\) с использованием блочной фильтрации (box filter). Значение результирующего пиксела \(R[i, j]\) равняется среднему арифметическому значений \(R_b\), попадающих в его пределы:

\[R[i, j] = \sum_{l = 1}^L s(R_b) / L,\]

где \(s(R_b)\) — выборочное значение (сэмпл), взятое с \(R_b\).

Стратегии семплирования

:scale 80% .small[https://en.wikipedia.org/wiki/Supersampling]

Аффинное преобразование

В системах двумерной визуализации данных фундаментальную роль играют аффинные преобразования.

Аффинное преобразование \(f\colon\mathbb{R}^{n}\to \mathbb{R}^{n}\) есть преобразование вида:

\[f(x) = M \cdot x + v,\]

где \(M\) — обратимая матрица (квадратная матрица, определитель которой отличен от нуля) и \(v\in \mathbb{R}^{n}\).

С помощью аффинных преобразований осуществляется навигация по карте: масштабирование, перемещение, поворот изображения.

Частные случаи этих операций могут быть связаны с центрированием относительно объекта, а также “вписыванием” объекта или множества объектов в пределы экрана.